package linkedListStack

import (
	"errors"
	"fmt"
	"strings"
)

type LinkedList[E any] struct {
	dummyHead *node[E]
	size      int
}

func MakeLinkedList[E any]() *LinkedList[E] {
	return &LinkedList[E]{
		dummyHead: makeNode[E](),
	}
}

// GetSize 获取链表中的元素个数
func (l *LinkedList[E]) GetSize() int {
	return l.size
}

// IsEmpty 返回链表是否为空
func (l *LinkedList[E]) IsEmpty() bool {
	return l.size == 0
}

// Add 在链表的index(0-based)位置添加新的元素e
// 索引操作，在链表中不是一个常用的操作，练习用
func (l *LinkedList[E]) Add(index int, e E) error {
	if index < 0 || index > l.size {
		return errors.New("add failed. Illegal index")
	}
	//获取添加索引的前一个节点
	prev := l.dummyHead
	for i := 0; i < index; i++ {
		prev = prev.next
	}
	prev.next = makeNode0(e, prev.next)
	l.size++
	return nil
}

// AddFirst 在链表头添加新的元素e
func (l *LinkedList[E]) AddFirst(e E) error {
	//newNode := makeNode1(e)
	//newNode.next = l.head
	//l.head = newNode
	return l.Add(0, e)
}

// AddLast 在链表末尾添加新的元素e
func (l *LinkedList[E]) AddLast(e E) error {
	//在index+1处添加节点
	return l.Add(l.size, e)
}

// Get 获得链表的第index(0-based)个位置的元素
// 索引操作，在链表中不是一个常用的操作，练习用
func (l *LinkedList[E]) Get(index int) (E, error) {
	var zero E
	if index < 0 || index >= l.size {
		return zero, errors.New("get failed. Illegal index")
	}
	//获取当前索引的节点
	cur := l.dummyHead.next
	for i := 0; i < index; i++ {
		cur = cur.next
	}
	return cur.e, nil
}

// GetFirst 获得链表的第一个元素
func (l *LinkedList[E]) GetFirst() (E, error) {
	return l.Get(0)
}

// GetLast 获得链表的最后一个元素
func (l *LinkedList[E]) GetLast() (E, error) {
	return l.Get(l.size - 1)
}

// Set 修改链表的第index(0-based)位置元素为e
// 索引操作，在链表中不是一个常用的操作，练习用
func (l *LinkedList[E]) Set(index int, e E) error {
	if index < 0 || index >= l.size {
		return errors.New("set failed. Illegal index")
	}
	//获取当前索引的节点
	cur := l.dummyHead.next
	for i := 0; i < index; i++ {
		cur = cur.next
	}
	cur.e = e
	return nil
}

// Remove 从链表中删除index(0-based)位置元素，返回删除的元素
// 索引操作，在链表中不是一个常用的操作，练习用
func (l *LinkedList[E]) Remove(index int) (E, error) {
	var zero E
	if index < 0 || index >= l.size {
		return zero, errors.New("remove failed. Illegal index")
	}
	//获取删除索引的前一个节点
	prev := l.dummyHead
	for i := 0; i < index; i++ {
		prev = prev.next
	}
	retNode := prev.next
	prev.next = retNode.next
	retNode.next = nil
	l.size--
	return retNode.e, nil
}

// RemoveFirst 从链表中删除第一个元素，返回删除的元素
func (l *LinkedList[E]) RemoveFirst() (E, error) {
	return l.Remove(0)
}

// RemoveLast 从链表中删除最后一个元素，返回删除的元素
func (l *LinkedList[E]) RemoveLast() (E, error) {
	return l.Remove(l.size - 1)
}

func (l *LinkedList[E]) String() string {
	sb := strings.Builder{}
	for cur := l.dummyHead.next; cur != nil; cur = cur.next {
		sb.WriteString(fmt.Sprintf("%s->", cur))
	}
	sb.WriteString("NULL")
	return sb.String()
}
